2016/08/04

Recent entries from same category

  1. Go 言語プログラミングエッセンスという本を書きました。
  2. errors.Join が入った。
  3. unsafe.StringData、unsafe.String、unsafe.SliceData が入った。
  4. Re: Go言語で画像ファイルか確認してみる
  5. net/url に JoinPath が入った。

記事中に間違いがありました。数倍も速くはなりませんでした。確か 1.0X ~ 1.1 倍程度の高速化は得られましたがびっくりするほどの物ではありませんでした。すみません。

そろそろ Go1.7 がリリースされるそうですが、皆さん如何お過ごしですか。Go 界隈の波平こと mattn ですこんにちわ。バカモー(略

Go1.7 ではコンパイラの最適化が行われ、ビルド速度がかなり短縮される様になりました。毎日ビルドしてる僕としては非常に嬉しい機能改善ですね。

さてとてもキャッチ―なタイトルで釣ってしまった訳ですが、気にしたら負けなのでどんどん話を進めます。

var t [256]byte

func f(b *[16]byte) {
    for i, v := range b {
        b[i] = t[v]
    }
}

例えばこのコードを見て下さい。このコードはココから拝借しました。issue の内容はスコープ外の t を参照している為、LEAQ がバイトコード出力されるのですがこれによりパフォーマンスが落ちるというもの。LEAQ とはスレッド固有変数にアクセスする為の x64 TLS 命令です。

例えば以下のコードを go tool compile -S foo.go でバイトコード出力します。

package main

var t [256]byte

func f(b []byte) {
    for i := 0; i < 100000000; i++ {
        b[i%len(b)] = t[i%len(t)]
    }
}

func main() {
}

すると以下のアセンブリが出力されます。

0x002f 00047 (s1.go:7)  TESTQ   CXCX
0x0032 00050 (s1.go:7)  JEQ $0, 149
0x0034 00052 (s1.go:7)  MOVQ    BXAX
0x0037 00055 (s1.go:7)  CMPQ    CX, $-1
0x003b 00059 (s1.go:7)  JEQ 144
0x003d 00061 (s1.go:7)  CQO
0x003f 00063 (s1.go:7)  IDIVQ   CX
0x0042 00066 (s1.go:7)  MOVQ    BXSI
0x0045 00069 (s1.go:7)  SARQ    $63BX
0x0049 00073 (s1.go:7)  MOVBQZX BLBX
0x004c 00076 (s1.go:7)  LEAQ    (SI)(BX*1), DI
0x0050 00080 (s1.go:7)  MOVBQZX DIBDI
0x0054 00084 (s1.go:7)  SUBQ    BXDI
0x0057 00087 (s1.go:7)  CMPQ    DI, $256
0x005e 00094 (s1.go:7)  JCC $0, 137
0x0060 00096 (s1.go:7)  LEAQ    "".t(SB), BX
0x0067 00103 (s1.go:7)  MOVBLZX (BX)(DI*1), BX
0x006b 00107 (s1.go:7)  CMPQ    DXCX
0x006e 00110 (s1.go:7)  JCC $0, 137
0x0070 00112 (s1.go:7)  MOVQ    "".b+8(FP), DI
0x0075 00117 (s1.go:7)  MOVB    BL, (DI)(DX*1)
0x0078 00120 (s1.go:6)  LEAQ    1(SI), BX
0x007c 00124 (s1.go:7)  MOVQ    DIDX
0x007f 00127 (s1.go:6)  CMPQ    BX, $100000000
0x0086 00134 (s1.go:6)  JLT $0, 47

ループ内で毎回 LEAQ を実行しているのが分かるかと思います。golang の場合、goroutine で外部から t を書き換えられる、もしくは t に nil を代入出来てしまう為、厳密にループ途中で新しい t を参照したり nil リファレンス例外を出すためにはループ内で LEAQ を使って毎回 t を参照しなければなりません。

しかし TLS 命令はある程度コストの掛かる命令です。そこで以下の1行を足します。

var t [256]byte

func f(b []byte) {
    t := t // ココ
    for i := 0; i < 100000000; i++ {
        b[i%len(b)] = t[i%len(t)]
    }
}

一見まったく意味のなさそうなコードに見えますが、これにより t が関数内に束縛され TLS 関数を使う必要がなくなります。もう一度アセンブリを見てみましょう。

0x0057 00087 (s2.go:7)  MOVQ    "".b+272(FP), AX
0x005f 00095 (s2.go:7)  MOVQ    $0, CX
0x0061 00097 (s2.go:7)  CMPQ    CX, $100000000
0x0068 00104 (s2.go:7)  JGE $0, 181
0x006a 00106 (s2.go:8)  MOVQ    CXDX
0x006d 00109 (s2.go:8)  SARQ    $63CX
0x0071 00113 (s2.go:8)  MOVQ    CXBX
0x0074 00116 (s2.go:8)  ANDQ    $15CX
0x0078 00120 (s2.go:8)  LEAQ    (DX)(CX*1), SI
0x007c 00124 (s2.go:8)  ANDQ    $15SI
0x0080 00128 (s2.go:8)  SUBQ    CXSI
0x0083 00131 (s2.go:8)  MOVBQZX BLCX
0x0086 00134 (s2.go:8)  LEAQ    (DX)(CX*1), BX
0x008a 00138 (s2.go:8)  MOVBQZX BLBX
0x008d 00141 (s2.go:8)  SUBQ    CXBX
0x0090 00144 (s2.go:8)  CMPQ    BX, $256
0x0097 00151 (s2.go:8)  JCC $0, 197
0x0099 00153 (s2.go:8)  MOVBLZX "".t(SP)(BX*1), CX
0x009d 00157 (s2.go:8)  TESTB   AL, (AX)
0x009f 00159 (s2.go:8)  CMPQ    SI, $16
0x00a3 00163 (s2.go:8)  JCC $0, 197
0x00a5 00165 (s2.go:8)  MOVB    CL, (AX)(SI*1)
0x00a8 00168 (s2.go:7)  LEAQ    1(DX), CX
0x00ac 00172 (s2.go:7)  CMPQ    CX, $100000000
0x00b3 00179 (s2.go:7)  JLT $0, 106

今度は t に関する LEAQ が消えました。実際にどれくらい効果があるのかベンチマークを書いてみました。

package main

import "testing"

var t [256]byte

func f1(b []byte) {
    for i := 0; i < 100000000; i++ {
        b[i%len(b)] = t[i%len(t)]
    }
}

func f2(b []byte) {
    t := t
    for i := 0; i < 100000000; i++ {
        b[i%len(b)] = t[i%len(t)]
    }
}

func BenchmarkWithLEAQ(b *testing.B) {
    var m [16]byte
    f1(m[:])
}

func BenchmarkWithoutLEAQ(b *testing.B) {
    var m [16]byte
    f2(m[:])
}

ベンチマークの実行は go test -bench . で行います。結果は以下の通り。

BenchmarkWithLEAQ-4                    1        1035500000 ns/op
BenchmarkWithoutLEAQ-4                 3         334666666 ns/op
PASS
ok      github.com/mattn/leaq   4.722s

たった1行で3倍1.0X倍から1.1倍程度のパフォーマンスアップが出来ました。この様に、並行でアクセス可能な変数をローカルで拘束する事で簡単に高速化が行えました。地味なテクニックですが手持ちの処理が遅くて困ってる人は一度試してみては如何でしょうか。なお、このテクニックはループ回数が多い場合に効いてきます。逆にループ回数が少ないと冒頭の LEAQ 分だけ損してしまう為、上記の f1/f2 を多い回数ループすると逆に f1 の方が速くなります。この辺はコンパイラの気持ちになって考えると答えが出てくるかもしれません。

変数のアトミック性を TLS を使って同期して実現してるのだと思ってましたが間違っていましたので記事を修正しました。
Posted at by